Color display devices that are used by computers and by computer-related devices such as digital cameras, generally comprise a two-dimensional matrix of display elements or pixels. Each pixel comprises a Red ("R"), Green ("G"), and Blue ("B") cell. Each display device cell is represented by a corresponding memory cell that may store a numeric value. The memory cell values usually are 8, 10, or 12 bits in size, and may be stored in any other convenient size. A computer program may cause a particular pixel to glow in any visible color, or to appear black or white, by setting the numeric values of its red, green, and blue cells to an appropriate value.
In many products and applications, some of the pixel information is generated or "interpolated" by a computer processor or CPU based on other information. Within the general field of computer graphics displays, there is an acute need to improve the way that displays generate or interpolate missing color information. In products that use display devices that are driven by a sensor, there is a particular need to improve the methods and mechanisms that are used to generate interpolated color information.
The following description will focus on particular problems encountered with digital cameras that use CCD sensors to receive light and form a digital picture for display by a color LCD display of the camera. However, the problems described herein occur in many other contexts, and the solutions described herein are applicable to such contexts. For example, the problems and solutions described herein are applicable to all color area sensors that use a two-dimensional array of sensing elements.
Generally, when a digital camera CPU receives image information from the camera sensor, each pixel provided by the sensor represents only one optical color, usually Red, Blue, or Green. The pixels are arranged in and arrive in a pattern, which corresponds to the physical placement of sensing elements in the sensor. In one pattern, a first line of the sensor has alternating Red and Green pixels, and the next line has alternating Green and Blue pixels. The pattern continues for the entire CCD sensor, which has a checkerboard or mosaic pattern.
FIG. 5 is a block diagram of a 7-by-7 portion 500 of sensor elements 502, 504, 506 that illustrates one pattern that is used by some CCD sensors. A first line 510 of portion 500 comprises a first Red pixel 502a, a first Green pixel 504a, a second Red pixel 502b, a second Green pixel 504b, and so on in an alternating pattern. Second line 512 of portion 500 has a first Green pixel 504c, a first Blue pixel 506a, a second Green pixel 504d, a second Blue pixel 506b, and so forth. This two-line pattern is repeated across the entire surface of the sensor. When the sensor delivers pixel information to a CPU or other clement, the information arrives in the same pattern.
Each pixel value may be an 8-bit quantity, 10-bit quantity, 12-bit quantity, or a numeric quantity of some other size. For convenience, in FIG. 5 each pixel is labeled with a numeral from 11 to 77 that identifies its relative position in the 7-by-7 portion 500.
In the foregoing pattern, there are twice as many Green pixels as there are Blue pixels or Red pixels. This is done because the human eye has been found to perceive Green as the most important color in an image, and also because the semiconductor materials that are used to form the sensors are less sensitive to light of Green wavelengths.
The pixel information receive using this checkerboard pattern, however, cannot be directly displayed on a graphic display device. An image may be produced only by adding further pixel information to the pattern of pixel information. Each element of the display comprises the combination of a Red, Green, and Blue pixel and corresponding pixel value, however, each element of the sensor represents only one of the three colors. Thus, two additional complementary color values must be generated and stored in association with the single color value received from the sensor.
For example, in the first line of the portion 500 of FIG. 5, for the first Red pixel 502a, Green and Blue color values must be created and stored. For the next pixel, which is Green pixel 504a, a Red value and a Blue value must be created and stored. This process is called "color interpolation" and must be rapidly carried out for every pixel value that is received from the sensor. An image may be displayed only after the interpolation step is complete.
Several past approaches are known for carrying out color interpolation. For example, bilinear interpolation involves an averaging approach. At each Blue pixel, to interpolate the Green value, the surrounding four (4) Green values actually received from the sensor are obtained, and their arithmetic mean is computed. The mean value becomes the interpolated Green value. This approach is simple, but relatively inaccurate in terms of color fidelity and image appearance.
A more accurate prior approach is bicubic color interpolation. Bicubic interpolation is similar to bilinear interpolation, but involves using more neighboring pixels and applying a computation that is more complex than averaging.
In one approach, the computation considers a 7-by-7 matrix of pixels, in which the pixel for which interpolation is carried out lies at the center of the matrix, and the computation considers three (3) neighbor pixels in each linear direction. For example, the matrix of FIG. 5 may be used. In this example, Blue pixel 41 is the center pixel for which interpolation is carried out and all other pixels illustrated in FIG. 5 are neighbors. In this approach, a corresponding matrix of coefficient values is defined and stored. Each coefficient has a floating-point value between "0" and "1". Each coefficient value is defined by a non-linear curve that reflects the relative contribution of each neighbor pixel to the complementary color values of the center pixel. Each coefficient value of all neighbor pixels of a particular color is multiplied by the value of the center pixel, then all the products are summed, and then the arithmetic mean of the products is taken. The result is the pixel value for that particular color.
FIG. 6 is a graph of one possible curve 600 of one line of the coefficient values. Vertical axis 602 represents the relative contribution of a particular pixel and therefore the magnitude of the coefficient. Horizontal axis 604 represents distance from the center pixel 41. Thus, generally, coefficient values decrease in a non-linear manner with increasing distance from the center pixel. In an embodiment, curve 600 is applied to a finite number of discrete coefficient values, such as seven, so that not all possible values of curve 600 are represented in the stored coefficients.
This approach has a significant disadvantage, namely that it is very computationally intensive. Referring to FIG. 5, assume that a bicubic interpolation process is executing, and that Blue pixel 41 is the pixel for which interpolation is currently being performed. Blue pixel 41 has twenty-four (24) non-zero Green neighbor pixels. Each Green neighbor pixel is associated with a co-efficient value having a value between "0" and "1". Thus, the approach would require considering 24 non-zero Green neighbor values and 24 associated coefficients.
Accordingly, this would require a CPU to perform 24 floating-point multiply operations to compute the contribution of each coefficient, and 23 add operations to yield a value for the Green color. The CPU would then have to compute the Red value. For Red and Green, a total of 40 floating-point multiplies and 30 adds are required. If the entire CCD sensor has 6 million pixels, this approach may take 10-12 seconds to carry out, which is unacceptably long. Thus, this approach is computationally too intensive for current microprocessors, especially when executed by the processors of the type now used in digital cameras and similar devices.
Other past approaches are described in J. A. Parker et al., "Comparison of Interpolating Methods for Image Resampling," MI-2 IEEE Transactions on Medical Imaging 31 (March 1983).
A related problem involves processing image data that is delivered serially from the sensor to a processor, for example the CPU of a digital camera.
A typical CCD camera sensor comprises an array of CCD sensors arranged in rows and columns. Between each column of CCDs there is a vertical shift register. At the bottom of all the columns is a horizontal shift register. When an image is formed by opening the shutter of the camera, each sensor in the array, which represents a pixel, is exposed for a length of time that is determined by a sensor controller. Then, information produced by all the sensors is transferred to the vertical shift registers. The information is then transferred, one pixel value at a time, to the horizontal shift register. The first pixel that is transferred corresponds to the upper left part of picture.
Thus, serial data is delivered from the sensor to a CPU, or to another hardware device such as photo processor 208 shown in FIG. 2. The CPU or other hardware device "sees" a line of pixel data comprising a Red value, Green value, Red value, Green value, and so forth. The next line of pixel data comprises alternating Green and Blue values. Generally, the lines are 1024 to 3000 pixels long, and the pixel data is delivered by the sensor at about 20 MHz.
Before the CPU or other device may carry out interpolation on the pixel data, the CPU must correct for any errors in each pixel value. For example, the CPU may carry out photo-response non-uniformity (PRNU) correction. PRNU correction generally involves multiplying pixel data that corresponds to a particular color by a correction factor or co-efficient that corrects for non-uniformity of the color filters of the CCD for that particular color. For example, it is known that certain semiconductor materials, from which the sensors are made, are more sensitive to red light than to blue light. PRNU correction adjusts for this variance in sensitivity.
After PRNU correction, a stream of corrected pixel data arrives at the CPU or other hardware device. The CPU may transfer the values to a memory, such as a high-performance SDRAM. The CPU may then begin carrying out interpolation of the missing color information. For example, the CPU may apply bicubic color interpolation using 7-by-7 blocks of memory. To obtain all the values needed to carry out interpolation for a particular pixel, however, the CPU must access 49 addresses in memory. Each access may involve computing an address and an offset value. If the data arrives at 20 MHz, just to keep up with the data stream, the CPU must operate with a memory clock cycle of at least 49.times.20 MHz, or 980 MHz. This is impractical for currently available SRAMs.
Thus, there is a need for an improved color interpolation approach that has a reduced computational burden.
In the field of digital cameras, there is a particular need for a color interpolation approach that can efficiently carry out color interpolation computations for digital images within the computation horsepower available in the digital camera.